package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code33SortList {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode cur = head;
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }

        ListNode dummyHead = new ListNode(-1, head);
        int mergeSize = 1;
        while (mergeSize < length) {
            // 每次都从头开始
            ListNode pre = dummyHead;
            cur = dummyHead.next;
            while (cur != null) {
                ListNode l1 = cur;
                for (int i = 0; i < mergeSize - 1 && cur.next != null; i++) {
                    cur = cur.next;
                }

                ListNode l2 = cur.next;
                // 断开链表1
                cur.next = null;
                cur = l2;
                for (int i = 0; i < mergeSize - 1 && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }

                // 记录下轮链表1的开始位置
                ListNode next = null;
                if (cur != null) {
                    next = cur.next;
                    // 断开链表2
                    cur.next = null;
                }

                pre.next = merge(l1, l2);
                while (pre.next != null) {
                    pre = pre.next;
                }

                cur = next;
            }
            if (mergeSize > (length >> 1)) {
                break;
            }
            mergeSize <<= 1;
        }
        return dummyHead.next;
    }

    public ListNode merge(ListNode h1, ListNode h2) {
        if (h1 == null) {
            return h2;
        }
        if (h2 == null) {
            return h1;
        }

        ListNode dummy = new ListNode(-1);
        ListNode l1 = h1;
        ListNode l2 = h2;
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        while (l1 != null) {
            cur.next = l1;
            l1 = l1.next;
            cur = cur.next;
        }
        while (l2 != null) {
            cur.next = l2;
            l2 = l2.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}
